package com.peng.leetcode.array;

import java.util.*;

/**
 * MaxEnvelopes
 * <p>
 * 354. 俄罗斯套娃信封问题
 * <p>
 * 首先按照数组的第一个元素排序，
 * 然后求解第二个元素的最长升序子序列。
 *
 * @author: lupeng6
 * @create: 2021/3/4 10:45
 */
public class MaxEnvelopes {

    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
//        int[][] envelopes = {{15, 22}, {8, 34}, {44, 40}, {9, 17}, {43, 23}, {4, 7}, {20, 8}, {30, 46}, {39, 36}, {45, 14}, {24, 19}, {24, 36}, {31, 34}, {32, 19}, {29, 13}, {16, 48}, {8, 36}, {44, 2}, {11, 5}, {2, 50}, {29, 6}, {18, 38}, {15, 49}, {22, 37}, {6, 20}, {25, 11}, {1, 50}, {19, 40}, {45, 35}, {37, 21}, {4, 29}, {40, 5}, {4, 49}, {1, 45}, {14, 32}, {14, 37}, {23, 22}, {31, 21}, {2, 36}, {43, 4}, {21, 32}, {41, 2}, {44, 32}, {36, 20}, {22, 45}, {3, 41}, {44, 29}, {29, 33}, {42, 2}, {38, 17}, {43, 26}, {30, 15}, {28, 12}, {33, 30}, {49, 7}, {8, 14}, {1, 9}, {41, 25}, {7, 15}, {26, 32}, {11, 33}, {12, 45}, {33, 7}, {16, 34}, {39, 1}, {20, 49}, {50, 45}, {14, 29}, {50, 41}, {1, 45}, {14, 43}, {49, 20}, {41, 37}, {43, 22}, {45, 19}, {20, 21}, {28, 19}, {2, 1}, {7, 49}, {3, 3}, {49, 48}, {34, 35}, {10, 2}};
        long start = System.currentTimeMillis();
        System.out.println(new MaxEnvelopes().maxEnvelopes(envelopes));
        System.out.println(System.currentTimeMillis() - start);
    }


    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        int len = envelopes.length;
        List<int[]> list = new ArrayList<>(len);
        for (int[] envelope : envelopes) {
            list.add(envelope);
        }
        Collections.sort(list, (e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e1[1] - e2[1];
            } else {
                return e1[0] - e2[0];
            }
        });

        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = list.get(i)[1];
        }
        int answer = maxSubArr(arr);
        return answer;
    }

    private int maxSubArr(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

}
